In the Integrated Circuit (IC) design, electronic components and wiring are represented by a set of geometric shapes and patterns from a physical perspective. A pattern is a set of polygon features in an area of an IC design. Electronic design automation (EDA) tools interact with these shapes and patterns throughout the IC design and verification process. For example, the patterns and shapes in the design are routinely checked with the Design Rules—Design Rules Checking (DRC). Design rules are a series of parameters provided by semiconductor manufacturers, specifying geometric and connectivity restrictions to ensure sufficient margins to account for variability in semiconductor manufacturing processes. DRC enables a designer to verify the correctness of his or her design and to achieve a high overall yield and reliability for the design.
However, when the lithography process reaches 65 nm and below, mere reliance on DRC may no longer be sufficient to ensure acceptable yields. One solution is the application of Lithography Process Checking (LPC). LPC simulates the actual lithography process on the design data to predict the eventual printed pattern on a silicon wafer. But lithography simulations are often costly and time-consuming. It is highly desirable to limit the number of simulations that must be performed for each design process. Patterns and shapes previously verified by lithography simulations could be stored in a database for the future use. When an EDA tool encounters a pattern, it may search the database for a matched pattern before conducting the expensive lithography simulations. If the search result turns out to be positive, then no simulation will be needed for this pattern. Pattern analysis and matching play an important role in this approach.
Pattern matching is the matching of all polygons and their vertices between two patterns. FIG. 1 illustrates the need for sorting in an approach for pattern matching. Although Pattern 100 and Pattern 102 are identical patterns, the vertices must be sorted or reordered such that the similarities between the patterns can be identified. For example, (x1,y1) of Pattern 100 does not match (x1, y1) of Pattern 102 but (x1,y1) of Pattern 100 does match (x5, y5) of Pattern 102. Therefore, the vertices in Pattern 100 and Pattern 102 need to be sorted so that the similarities between the patterns are apparent. However, the sorting and comparison approach results in an expense on the order of n log n, where n is the number of vertices of the objects in a pattern. Further, a large amount of memory is required to store all of the vertices for large patterns in order to perform the comparisons alone. Thus, there is a need to reduce the cost involved in pattern matching with improved pattern signatures.